翻訳と辞書 Words near each other ・ Pohl & Kornbluth ・ Pohl trial ・ Pohl, Germany ・ Pohla, Estonia ・ Pohle ・ Pohle (disambiguation) ・ Pohle's fruit bat ・ Pohled (Havlíčkův Brod District) ・ Pohledy ・ Pohlern ・ Pohleď ・ Pohlheim ・ Pohlia scotica ・ Pohlidium ・ Pohlig ・ Pohlig–Hellman algorithm ・ Pohlitz Township, Roseau County, Minnesota ・ Pohlmann ・ Pohlmann's Hall ・ Pohlmeyer charge ・ Pohlsepia ・ Pohneh Kargav ・ Pohnpei ・ Pohnpei fantail ・ Pohnpei flycatcher ・ Pohnpei International Airport ・ Pohnpei kingfisher ・ Pohnpei lorikeet ・ Pohnpei starling ・ Pohnpei State Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Pohlig–Hellman algorithm ： ウィキペディア英語版 Pohlig–Hellman algorithm In number theory, the Pohlig–Hellman algorithm sometimes credited as the Silver–Pohlig–Hellman algorithm〔Mollin 2006, pg. 344〕 is a special-purpose algorithm for computing discrete logarithms in a multiplicative group whose order is a smooth integer. The algorithm was discovered by Roland Silver, but first published by Stephen Pohlig and Martin Hellman (independent of Silver). We will explain the algorithm as it applies to the group Z *''p'' consisting of all the elements of Z''p'' which are coprime to ''p'', and leave it to the advanced reader to extend the algorithm to other groups by using Lagrange's theorem. :Input Integers ''p'', ''g'', ''e''. :Output An Integer ''x'', such that ''e'' ≡ ''g''''x'' (mod ''p'') (if one exists). :#Determine the prime factorization of the order of the group : $\backslash varphi(p)=\; p\_1\backslash cdot\; p\_2\; \backslash cdots\; p\_n$ (All the ''p''''i'' are considered small since the group order is smooth.) :#From the Chinese remainder theorem it will be sufficient to determine the values of ''x'' modulo each prime power dividing the group order. Suppose for illustration that ''p''1 divides this order but ''p''12 does not. Then we need to determine ''x'' mod ''p''1, that is, we need to know the ending coefficient ''b''1 in the base-''p1'' expansion of ''x'', i.e. in the expansion ''x'' = ''a''1 ''p''1 + ''b''1. We can find the value of ''b1'' by examining all the possible values between 0 and ''p''1-1. (We may also use a faster algorithm such as baby-step giant-step when the order of the group is prime.〔Menezes, et. al 1997, pg. 109〕) The key behind the examination is that: $$ \begine^ & \equiv (g^x)^ \pmod \\ & \equiv (g^)^g^ \pmod \\ & \equiv (g^)^ \pmod \end (using Euler's theorem). With everything else now known, we may try each value of ''b''1 to see which makes the equation be true. If $g^\; \backslash not\backslash equiv\; 1\; \backslash pmod$, then there is exactly one ''b''1, and that ''b''1 is the value of ''x'' modulo ''p''1. (An exception arises if $g^\; \backslash equiv\; 1\; \backslash pmod$ since then the order of ''g'' is less than φ(''p''). The conclusion in this case depends on the value of $e^\; \backslash mod\; p$ on the left: if this quantity is not 1, then no solution ''x'' exists; if instead this quantity is also equal to 1, there will be more than one solution for ''x'' less than φ(''p''), but since we are attempting to return only one solution ''x'', we may use ''b''1=0.) :#The same operation is now performed for ''p''2 through ''pn''. A minor modification is needed where a prime number is repeated. Suppose we are seeing ''pi'' for the (''k'' + 1)st time. Then we already know ''ci'' in the equation ''x'' = ''a''''i'' ''p''''i''''k''+1 + ''b''''i'' ''p''''i''''k'' + ''c''''i'', and we find either ''b''''i'' or ''c''''i'' the same way as before, depending on whether $g^\; \backslash equiv\; 1\; \backslash pmod$. :# With all the ''b''''i'' known, we have enough simultaneous congruences to determine ''x'' using the Chinese remainder theorem. ==Complexity== The worst-case time complexity of the Pohlig–Hellman algorithm is $O(\backslash sqrt\; n)$ for a group of order ''n'', but it is more efficient if the order is smooth. Specifically, if $\backslash prod\_i\; p\_i^$ is the prime factorization of ''n'', then the complexity can be stated as $O\backslash left(\backslash sum\_i\; \backslash right)$.〔Menezes, et. al 1997, pg. 108〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pohlig–Hellman algorithm」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.